package golk

import "container/heap"

type entry struct{ i, j, val int }
type hp2 []entry

func (h hp2) Len() int            { return len(h) }
func (h hp2) Less(i, j int) bool  { return h[i].val < h[j].val }
func (h hp2) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *hp2) Push(v interface{}) { *h = append(*h, v.(entry)) }
func (h *hp2) Pop() interface{}   { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }

type pair struct{ x, y int }

var dirs = []pair{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

func swimInWater(grid [][]int) (ans int) {
	n := len(grid)
	vis := make([][]bool, n)
	for i := range vis {
		vis[i] = make([]bool, n)
	}
	vis[0][0] = true
	h := &hp2{{0, 0, grid[0][0]}}
	for {
		e := heap.Pop(h).(entry)
		ans = max(ans, e.val)
		if e.i == n-1 && e.j == n-1 {
			return
		}
		for _, d := range dirs {
			if x, y := e.i+d.x, e.j+d.y; 0 <= x && x < n && 0 <= y && y < n && !vis[x][y] {
				vis[x][y] = true
				heap.Push(h, entry{x, y, grid[x][y]})
			}
		}
	}
}

func max2(a, b int) int {
	if a > b {
		return a
	}
	return b
}
